package com.cfc.stage1;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: 最长回文子串
 *   https://leetcode.cn/problems/longest-palindromic-substring/
 * @author: yangxuan10
 * @create: 2024-05-24 09:06
 **/
public class LongestPalindrome {

    @Test
    public void test1() {
        System.out.println(longestPalindrome1("bacabab"));
    }

    /**
     * 原创二 我觉得相较于第一个这个可以了呢，但是....还是慢啊
     * @param s
     * @return
     */
    public String longestPalindrome1(String s) {
        if ( s == null || s.length() == 0) {
            return "";
        }
        char[] chars = s.toCharArray();
        String longestPalindrome = ""+chars[0];
        for (int i = 0; i < chars.length-1; i++) {
            if (longestPalindrome.length() >= (chars.length -i)) {
                break;
            }
            char front = chars[i];
            String sonPalindromeStr = front+"";
            List<String> list = new ArrayList<>();
            for (int j = i+1; j < chars.length; j++) {
                sonPalindromeStr+=chars[j];
                if (front == chars[j] && sonPalindromeStr.length() > longestPalindrome.length()) {
                    list.add(sonPalindromeStr);
                }
            }
            for (int j = list.size()-1; j >=0; j--) {
                boolean palindrome = isPalindrome(list.get(j));
                if (palindrome) {
                    longestPalindrome = list.get(j);
                    break;
                }
            }
        }
        return longestPalindrome;
    }


    /**
     * 原创一： 每次都调用检查是否是回文字符串，太慢了
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if ( s == null || s.length() == 0) {
            return "";
        }
        char[] chars = s.toCharArray();
        String longestPalindrome = ""+chars[0];
        for (int i = 0; i < chars.length-1; i++) {
            if (longestPalindrome.length() >= (chars.length -i)) {
                break;
            }
            char front = chars[i];
            String sonPalindromeStr = front+"";
            for (int j = i+1; j < chars.length; j++) {
                sonPalindromeStr+=chars[j];
                if (front == chars[j]) {
                    //FIXME 这里每次都调用检查是否是回文字符串，太慢了
                    boolean palindrome = isPalindrome(sonPalindromeStr);
                    if (palindrome && sonPalindromeStr.length() > longestPalindrome.length()) {
                        longestPalindrome = sonPalindromeStr;
                    }
                }
            }
        }
        return longestPalindrome;
    }

    public boolean isPalindrome(String x1) {
        char[] chars = x1.toCharArray();
        int length = chars.length;
        int startIndex = 0;
        int endIndex = length -1;
        while (true) {
            if (startIndex >= endIndex) {
                break;
            }
            if (chars[startIndex] != chars[endIndex]) {
                return false;
            }
            startIndex++;
            endIndex--;
        }
        return true;
    }

}